1. Technical Field
The present application relates generally to an improved data processing system and method. More specifically, the present application is directed to a system and method for reducing memory overhead of a page table in a dynamic logical partitioning environment.
2. Description of Related Art
Virtual memory mechanisms provide the ability to simulate more memory than actually exists in a computing system, thereby allowing the computing system to run larger programs or more programs concurrently. Virtual addressing provides a separation between the physical memory and the addresses that a program accesses to load or store data. One of the common uses of this separation is to facilitate paging to disk, which allows an operating system to make efficient use of primary memory, i.e. a volatile memory such as a RAM, by moving unused instructions and data into secondary memory, i.e. a non-volatile memory such as a hard disk, and then re-allocating the physical memory to another process.
When the original process references the virtual address where it expects its instructions or data to be, the operating system re-allocates physical primary memory (possibly having to move some additional primary memory to secondary memory), then moves these instructions and data back to this primary memory.
Virtual addressing provides many other benefits. One of the most important benefits of virtual addressing is that each process can write only to the physical memory for which the operating system has created page table entries. This prevents one process from overwriting another process's data.
As an example of virtual addressing, assume a computer architecture where a word size is 32 bits. This means addresses may be formed from 0x00000000 to 0xffffffff—spanning 4 GB. These addresses form what is called as the “virtual address space.” These addresses have no physical meaning, i.e. if only 16 MB of memory is available, all addresses above 0x01000000 would be invalid. However, most programs do not use all 4 GB of memory when a program runs, but only parts of it at a time.
The 4 GB virtual address space is split up into chunks, commonly 4 KB in size, referred to as pages. The physical memory is also split up into chunks, also commonly 4 KB in size, referred to as “frames.” A program's text segment might start at the virtual address 0x00000004—page number 0x0, and offset 0x4, but in reality, this may correspond to the physical address 0xff0e0004—frame number 0xff0e, and offset 0x4. What the virtual memory mechanism does is convert virtual addresses into physical addresses, essentially, mappings between pages and frames. The page table is used for this purpose.
FIG. 1 illustrates the use of a page table for mapping between pages and frames in accordance with a known architecture. Assume that a program is running and it tries to access memory in the virtual address 0xd09fbabe. The virtual address has two main portions, 0xd09f is the page number and 0xbabe is the offset within the page 0xd09f.
The virtual address (usually only the virtual page identifier portion of the virtual address), is first checked for validity, i.e. whether the address is within the valid virtual address ranges of the program. If the address is invalid, a processor interrupt occurs and the operating system sends a segmentation fault message and subsequently terminates the offending program. If the address is valid, the address is looked up within a translation lookaside buffer (TLB) 110. The TLB 110 is specifically designed to perform this lookup in parallel so as to provide an extremely fast lookup process. If there is a match for page 0xd09f within the TLB 110, i.e. a TLB “hit,” the physical frame number is retrieved, the offset replaced, and the memory access can continue. However, if there is no match, i.e. a TLB “miss,” the second mechanism checked is the page table 120.
When the hardware, i.e. the TLB 110, is unable to find a physical frame for a virtual page, i.e. there is a TLB miss, the processor initiates a “table walk” to essentially perform a look-up of the appropriate page table 120 in main memory (there is a separate page table for each logical partition utilized in the data processing system, as discussed hereafter). This “table walk” is performed completely in hardware, i.e. without any software involvement, each time there is a TLB miss.
The “table walk” looks up the hardware page table in main memory and determines if there is a valid translation (from virtual page identifier to physical identifier) found. If a valid translation is found, which occurs more often than not, the translation information is loaded into the TLB. The processor may then restart the instruction that caused the TLB miss.
If the “table walk” operation does not find a valid page translation, or mapping, entry in a hardware page table, then the hardware will generate a processor interrupt called a “page fault.” Hardware architectures offer the chance for an interrupt handler 130 to be installed by the operating system to deal with such page faults. The interrupt handler 130 can look up the address mapping in the page table 120, and can see whether a mapping exists in the page table 120. If one exists, it is written back to the TLB 110, as the hardware accesses memory through the TLB 110 in a virtual memory system, and the faulting instruction is restarted, with the consequence that the hardware will look in the TLB 110 again, find the mapping, and the translation will succeed.
However, the page table lookup may not be successful for two reasons. First there may not be a translation available for that address and thus, the memory access to that virtual address is bad or invalid. Second, the page is not resident in physical memory.
In the first case, the memory access is invalid, and the operating system must take some action to deal with the problem. On modern operating systems, it will send a segmentation fault to the offending program. In the second case, the page is normally stored elsewhere, such as on a hard disk 140. To handle this case, the page needs to be taken from the hard disk 140 and put into physical memory. When physical memory is not full, this is quite simple, one simply needs to write the page into physical memory, modify the entry in the page table 120 to say that it is present in physical memory, write the mapping into the TLB 110 and restart the instruction.
However, when physical memory is full, and there are no free frames available, pages in physical memory may need to be swapped with the page that needs to be written to physical memory. The page table 110 needs to be updated to mark that the pages that were previously in physical memory are no longer so, and to mark that the page that was on the hard disk 140 is no longer so also (and to of course write the mapping into the TLB 110 and restart the instruction).
While the page table provides a convenient mechanism for mapping between virtual addresses and real physical memory addresses, a large amount of main memory is needed for storing the page table. Such memory requirements become even more of a concern in logically partitioned computing environments where the logical partitions of the system must each have their own page table. The memory overhead for the page tables for each of the logical partitions can become a substantial portion of the total main memory.
When creating a new logical partition in a logical partition (LPAR) environment, such as a shared processor LPAR (SPLPAR), a portion of main memory is allocated for the page table for the new LPAR. The size of the portion of memory allocated for the page table is proportional to the total main memory allocated to the partition. Since memory cannot be shared among LPARs, the total amount of main memory allocated to all partitions is no more than the total amount of main memory in the computing system. Therefore, the total amount of main memory allocated to page tables of all the LPARs should not be more than for the same system without the LPARs. In other words, the memory overhead due to page tables is no worse for a SPLPAR computing system than for a conventional non-LPAR computing system.
However, by introducing the additional functionality of dynamic LPARs, where the computing system can increase or decrease the amount of main memory allocated to a LPAR dynamically, the total memory overhead of page tables of all LPARs may increase to be much larger than the conventional non-LPAR computing system. This is because when the page table is allocated for a newly created LPAR, the page table size is not allocated based on the main memory actually allocated to the LPAR upon its creation, but instead the page table size is made large enough to accommodate the maximum main memory that may be dynamically allocated to the LPAR during its lifetime.
The main purpose of dynamic LPAR is to rebalance the computing system's hardware resources, main memory included, to better accommodate the daily, weekly, or unexpected large fluctuation of workloads among applications running in different LPARs of the same computing system. To effectively take advantage of this flexibility of resource balancing, it is common that a LPAR declare a much larger main memory limit than it asks for and is allocated at the LPAR creation time. Consequently, the total maximum memory size of all the LPARs, and thus, the total memory size of their page tables, may be much larger than the conventional non-LPAR computing system configuration.
For example, in known architectures the memory overhead ration of a page table to the associated main memory is 1:64, i.e. 1 GB of page table is required to accommodate 64 GB of main memory. If the dynamic range of the main memory allowed for each partition is 10X, the memory overhead of the page table alone becomes 10 GB, or about ⅙th of all the main memory. This is a substantial portion of the total available main memory.
Known solutions for addressing this memory overhead problem include not allowing dynamic LPAR functionality. This completely solves the problem of memory overhead associated with dynamic LPAR since the functionality is not permitted to exist. However, as a result, the computing system can potentially be much less utilized after it loses the ability to load-balance the memory resource. This defeats one of the original major purposes of using LPAR environments.
Another known solution is to dynamically create a new page table when the total amount of main memory allocated to a LPAR is changed. As a result, it is not necessary to specify the size of the page table to be the maximum size required throughout the lifetime of the LPAR.
With this solution, although the computing system does not need to be shutdown for this solution, there will typically be a very long delay before a page table is completely created from scratch with a change in the LPAR. During this time period, the LPAR associated with the page table being created cannot perform useful work. For computing systems that have to meet established quality of service requirements, which typically do not allow extended periods of no service, this is not a feasible solution.